﻿// https://newcoder.com  连续子数组的最大和
//描述
//输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
//数据范围 :
//1 <= n <= 2\times10 ^ 51 <= n <= 2×105
//- 100 <= a[i] <= 100−100 <= a[i] <= 100
//要求:时间复杂度为 O(n)O(n)，空间复杂度为 O(n)O(n)
//进阶 : 时间复杂度为 O(n)O(n)，空间复杂度为 O(1)O(1)
//输入：
//[1, -2, 3, 10, -4, 7, 2, -5]
//经分析可知，输入数组的子数组[3, 10, -4, 7, 2]可以求得最大和为18


//class Solution {
//public:
//    int FindGreatestSumOfSubArray(vector<int> array) {
//        //解题思路：
//        //方法一：我们可以使用dp完成
//        //定义状态# f(i): 以i下标结尾的最大连续子序列的和
//        //状态递推：f(i) = max(f(i-1)+array[i], array[i]) 【这里一定要注意连续关键字】
//        //状态初始化：f(0) = array[0], max = array[0]
//
//        vector<int> f(array.size());
//        f[0] = array[0];
//        int ret = f[0];
//        for (int i = 1; i < array.size(); i++) {
//            f[i] = max(f[i - 1] + array[i], array[i]);
//            if (ret < f[i]) ret = f[i];
//        }
//
//        return ret;
//    }
//};

